//底层由节点实现的线性表(链表)
public class LinkedList<E> {
    //节点的定义
    private class Node {
        E data;     //数据域 默认null
        Node next;  //指针域 默认null
    }
    private Node head;  //头指针
    private Node tail;  //尾指针
    private int size;   //元素个数

    public LinkedList() {
        size = 0;
        head = null;
        tail = null;
    }

    public void add(E element) {
        add(size, element);
    }

    public void add(int index, E element){
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("角标越界!");
        }
        Node node = new Node();
        node.data = element;
        if (isEmpty()) {
            head = node;
            tail = node;
        } else if (index == 0) {
            node.next = head;
            head = node;
        } else if (index == size) {
            tail.next = node;
            tail = node;
        } else {
            Node p = head;
            for (int i = 0; i < index - 1; i++) {
                p = p.next;
            }
            node.next = p.next;
            p.next = node;
        }
        size++;
    }

    public E remove(int index){
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("角标越界!");
        }
        E ret = null;
        if (size == 1) {
            ret = head.data;
            head = null;
            tail = null;
        }else if (index == 0) {
            ret = head.data;
            Node node = head;
            head = head.next;
            node.next = null;
        } else if (index == size - 1) {
            ret = tail.data;
            Node p = head;
            while (p.next != tail) {
                p = p.next;
            }
            p.next = null;
            tail = p;
        } else {
            Node p = head;
            for (int i = 0; i < index - 1; i++) {
                p = p.next;
            }
            Node node = p.next;
            ret = node.data;
            p.next = node.next;
            node.next = null;
        }
        size--;
        return ret;
    }

//    public E get(int index){}

//    public E set(int index, E element){}

//    public int indexOf(E element){}

    public boolean isEmpty(){
        return size == 0 && head == null && tail == null;
    }

//    public int size() {}

//    @Override
//    public String toString() {}
}